package org.fly.alg;

import java.util.ArrayList;
import java.util.List;

public class CharTrie {
    private char data;
    private List<CharTrie> children;
    
    public CharTrie() {
        this(' ');
    }
    
    public CharTrie(char data) {
        this.data = data;
    }
    
    public boolean insert(String str) {
        return insert(str, 0);
    }
    
    public boolean insert(String str, int index) {
        Pair<CharTrie, Integer> result = find(str, index);
        if (result.getSecond() == str.length()) {
            return false;
        }
        result.getFirst().add(str, result.getSecond());
        return true;
    }
    
    public boolean contains(String str) {
        return find(str, 0).getSecond() == str.length();
    }
    
    private void add(String str, int index) {
        if (str.length() == index) {
            return;
        }
        if (children == null) {
            children = new ArrayList<CharTrie>();
        }
        CharTrie trie = new CharTrie(str.charAt(index));
        trie.add(str, ++index);
        children.add(trie);
    }

    private Pair<CharTrie, Integer> find(String str, int index) {
        if (null == children || index == str.length()) {
            return new Pair<CharTrie, Integer>(this, index);
        }
        for (CharTrie child : children) {
            if (child.data == str.charAt(index)) {
                return child.find(str, ++index);
            }
        }
        return new Pair<CharTrie, Integer>(this, index);
    }
}